/********************************************
Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

Subscribe to see which companies asked this question
********************************************/
#include <stdio.h>
#include <stdlib.h>

struct ListNode{
	int val;
	struct ListNode* next;
};

void setList(struct ListNode* head, int val)
{
	struct ListNode *q;
	q = head;
	while(q->next != NULL)
		q = q->next;
	
	struct ListNode *tmp = (struct ListNode *)malloc(sizeof(struct ListNode));
	if(tmp == NULL)
		return;
	tmp->val = val;
	tmp->next = q->next;
	q->next = tmp;
}

void print(struct ListNode* head)
{
	struct ListNode* p;
	for(p = head; p != NULL; p = p->next)
	{
		printf("[%d]", p->val);
	}
	printf("\n");
}

struct ListNode* reverseList(struct ListNode* head) {
    if(head == NULL || NULL == head->next)
		return head;

	struct ListNode* pPre = NULL;
	struct ListNode* pPoint = NULL;
	struct ListNode* pHead = (struct ListNode*)malloc(sizeof(struct ListNode));
	if(NULL == pHead)
		return NULL;
	pHead->next = head;
	pPoint = head->next;
	head->next = NULL;

	while(pPoint != NULL)
	{
		pPre = pHead->next;
		pHead->next = pPoint;

		pPoint = pPoint->next;

		pHead->next->next = pPre;
	}
	return pHead->next;
	
}


void main(void)
{
	struct ListNode* head;
	int num[] = {2,1};
	int i;
	int val = 2;
	head = (struct ListNode*)malloc(sizeof(struct ListNode));
	head->next = NULL;
	head->val = num[0];
	for(i = 1; i < sizeof(num)/sizeof(int); i++)
		setList(head, num[i]);
	print(head);
	print(reverseList(head));
}

